#include <vector>
#include <string>

using namespace std;

// 思路： DFS + 回溯

class Solution
{
public:
    // 先分割，再半段是不是回文串
    vector<vector<string>> partition(string s)
    {
        vector<vector<string>> res;
        vector<string> temp;
        dfs(s, 0, res, temp);
        return res;
    }
    // dfs 判断当前index开始的子串 是不是回文串
    // index表示当前子串的起始位置
    // i表示当前子串的结束位置
    // temp存储当前的回文子串
    // res存储最终的结果
    void dfs(string s, int index, vector<vector<string>> &res, vector<string> &temp)
    {
        if (index >= s.size()) // 为什么是等于号 因为index是从0开始的
        {
            res.push_back(temp);
            return;
        }
        for (int i = index; i < s.size(); ++i) // i是子串的结束位置
        {
            if (isHW(s, index, i))
            {
                temp.push_back(s.substr(index, i - index + 1));
                dfs(s, i + 1, res, temp);
                temp.pop_back();
            }
        }
    }
    bool isHW(string &s, int left, int right)
    {
        while (left < right)
        {
            if (s[left] == s[right])
            {
                ++left;
                --right;
            }
            else
            {
                return false;
            }
        }
        return true;
    }
};